package 数组;
import java.util.*;
/**
 * 该类用于在数组中查找重复元素。
 * 提供三种查找方式：使用哈希集合、排序后查找、快慢指针。
 */
public class findDuplicate {
    /**
     * 使用哈希集合查找重复元素。
     * @param nums 输入数组
     * @return 重复元素，若不存在则返回-1
     */
    public int findDupSet(int[] nums){
        HashSet<Integer> set = new HashSet<>();
        for(int num : nums){
            boolean flag = set.add(num);
            if(flag == false) return num; // 如果添加失败，说明元素重复
        }
        return -1;
    }

    /**
     * 使用排序后查找重复元素。
     * @param nums 输入数组
     * @return 重复元素，若不存在则返回-1
     */
    public int findDupSort(int[] nums){
        // Arrays.sort(nums);
        quickSort(nums, 0, nums.length - 1); // 使用快速排序
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i - 1]) return nums[i]; // 如果相邻元素相等，说明重复
        }
        return -1;
    }

    /**
     * 快速排序算法。
     * @param nums 待排序数组
     * @param left 左边界
     * @param right 右边界
     */
    private void quickSort(int[] nums, int left, int right){
        if(left >= right) return; // 如果左边界大于等于右边界，返回
        int pivot = partition(nums, left, right); // 获取基准元素的位置
        quickSort(nums, left, pivot - 1); // 递归排序左半部分
        quickSort(nums, pivot + 1, right); // 递归排序右半部分
    }

    /**
     * 分区函数，用于快速排序。
     * @param nums 待排序数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的位置
     */
    private int partition(int[] nums, int left, int right){
        int val = nums[left]; // 选择第一个元素作为基准
        while(left < right){
            while(left < right && nums[right] >= val) right--; // 从右向左找小于基准的元素
            nums[left] = nums[right]; // 将小于基准的元素放到左边
            while(left < right && nums[left] <= val) left++; // 从左向右找大于基准的元素
            nums[right] = nums[left]; // 将大于基准的元素放到右边
        }
        nums[left] = val; // 将基准元素放到最终位置
        return left; // 返回基准元素的位置
    }

    /**
     * 使用快慢指针查找重复元素。
     * @param nums 输入数组
     * @return 重复元素
     */
    public int findDupSlowFast(int[] nums){
        int slow = 0;
        int fast = 0;
        slow = nums[slow]; // 慢指针移动一步
        fast = nums[nums[fast]]; // 快指针移动两步
        while(slow != fast){ // 当快慢指针相遇时，说明存在环
            slow = nums[slow]; // 慢指针移动一步
            fast = nums[nums[fast]]; // 快指针移动两步
        }
        int p1 = 0; // 从头开始
        int p2 = slow; // 从相遇点开始
        while(p1 != p2){ // 当两个指针相遇时，即为重复元素
            p1 = nums[p1]; // 移动p1
            p2 = nums[p2]; // 移动p2
        }
        return p1; // 返回重复元素
    }

    /**
     * 主方法，处理输入并输出结果。
     * 输入：一行逗号分隔的数组
     * 输出：三种查找方式的结果
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(",");
        int[] nums = new int[s.length];
        for(int i = 0; i < s.length; i++){
            nums[i] = Integer.parseInt(s[i]);
        }
        findDuplicate fd = new findDuplicate();
        System.out.println("set:" + fd.findDupSet(nums)); // 输出哈希集合查找的结果
        System.out.println("sort:" + fd.findDupSort(nums)); // 输出排序后查找的结果
        System.out.println("ptr:" + fd.findDupSlowFast(nums)); // 输出快慢指针查找的结果
        sc.close();
    }
}
